home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Snippets / fastsort / fastsort.c next >
Encoding:
C/C++ Source or Header  |  1994-05-10  |  3.5 KB  |  183 lines  |  [TEXT/R*ch]
  1. /*
  2. *
  3. * fastsort - sort a file in place - fast!
  4. *
  5. * Written 03/01/89 by Edwin R. Carp
  6. *
  7. * Copyright 1989 by Edwin R. Carp
  8. *
  9. *
  10. * John F. Haugh II, modified 3/3/89
  11. *
  12. * Completely rehacked to remove the two pass garbage
  13. * and quit pushing strings about in memory.  Reads
  14. * entire file in with one call, splits into lines and
  15. * saves pointers to each.  Then sorts pointers and
  16. * outputs lines.
  17. *
  18. * No big deal ...
  19. *
  20. *
  21. * Terence M. Donahue, modified 3/4/89
  22. *
  23. * Uses fputs() instead of fprintf() to output the sorted lines
  24. * Inlined the string compare into the compare() function.
  25. *
  26. * It is now about as fast as sort on my machine...
  27. *
  28. * There is a slow homemade quicksort routine #ifdef'ed out.
  29. * Once it is fast enough, compile -DHOMEMADE to have it replace qsort
  30. */
  31.  
  32. #include <stdio.h>
  33. #include <sys/types.h>
  34. #include <sys/stat.h>
  35. #include <fcntl.h>
  36.  
  37. nomem (s)
  38. char    *s;
  39. {
  40.     fprintf (stderr, "Can't get memory for %s\n", s);
  41.     exit (1);
  42. }
  43.  
  44. #ifdef HOMEMADE
  45. /*
  46. ** This homemade quicksort is currently much slower than qsort,
  47. ** especially for large arrays.
  48. **
  49. ** Future improvements:
  50. **
  51. **    inline the strcmps
  52. **    do the recursive sort call on the smaller partition
  53. **    switch to an insertion sort on partitions smaller than 8 elements
  54. */
  55.  
  56. #define exch(x,y) (temp = x, x = y, y = temp)
  57.  
  58. void sort(v,left,right)
  59.      char *v[];
  60.      int left,right;
  61. {
  62.   int i, last;
  63.   char *temp;
  64.  
  65.   while (left < right) {
  66.     /* Determine pivot by taking the median of left, middle, and right */
  67.     i = (left+right)>>1;
  68.     if (strcmp(v[left],v[right]) > 0) {
  69.       if (strcmp(v[left],v[i]) < 0)       i = left;
  70.       else if (strcmp(v[right],v[i]) > 0) i = right;
  71.     }
  72.     else {
  73.       if (strcmp(v[left],v[i]) > 0)       i = left;
  74.       else if (strcmp(v[right],v[i]) < 0) i = right;
  75.     }
  76.  
  77.     exch(v[left],v[i]);
  78.  
  79.     last = left;
  80.     for (i=left+1; i <= right; i++)
  81.       if (strcmp(v[i],v[left]) < 0)
  82.     if (i != ++last) { exch(v[last],v[i]); }
  83.  
  84.     exch(v[left],v[last]);
  85.  
  86.     if (left < last-1) sort(v, left, last-1);
  87.     left = last+1;
  88.   }
  89. }
  90.  
  91. #else
  92.  
  93. compare(sp1,sp2)
  94.      char **sp1,**sp2;
  95. {
  96.   char *s1,*s2;
  97.  
  98.   s1 = *sp1; s2 = *sp2;
  99.   while(*s1 == *s2++)
  100.     if(*s1++ == '\0') return 0;
  101.   return(*s1 - *--s2);
  102. }
  103. #endif
  104.  
  105. main(argc, argv)
  106. int argc;
  107. char **argv;
  108. {
  109.     int    fd;
  110.     char    *malloc ();
  111.     char    *realloc ();
  112.     char    *cp;
  113.     char    *buf;
  114.     char    **lines;
  115.     int    cnt, cur, max;
  116.     struct    stat    statbuf;
  117.     FILE    *fp;
  118.  
  119.     if (argc < 2) {
  120.         fprintf (stderr, "usage: fastsort files ...\n");
  121.         exit (1);
  122.     }
  123.     while (*++argv) {
  124.         if (stat (*argv, &statbuf)) {
  125.             perror(*argv);
  126.             continue;
  127.         }
  128.         if (! (buf = malloc ((unsigned) statbuf.st_size + 1)))
  129.             nomem (*argv);
  130.  
  131.         if ((fd = open (*argv, O_RDONLY)) < 0) {
  132.             perror (*argv);
  133.             continue;
  134.         }
  135.         if (read (fd, buf, statbuf.st_size) != statbuf.st_size) {
  136.             perror (*argv);
  137.             free (buf);
  138.             continue;
  139.         }
  140.         close (fd);
  141.  
  142.         *(cp = &buf[statbuf.st_size]) = '\0';
  143.  
  144.         cur = 0;
  145.         max = 10;
  146.  
  147.         if (! (lines = (char **) malloc (sizeof (char *) * max)))
  148.             nomem (*argv);
  149.  
  150.         while (--cp != buf) {
  151.             if (*cp == '\n') {
  152.                 *cp = '\0';
  153.                 if (cur == max)
  154.                     if (! (lines = (char **) realloc (lines, sizeof (char *) * (max += 10))))
  155.                         nomem (*argv);
  156.                 lines[cur++] = cp + 1;
  157.             }
  158.         }
  159.         lines[0] = buf;        /* fix our earlier mistake :-) */
  160.  
  161. #ifdef HOMEMADE
  162.         sort (lines, 0, cur-1);
  163. #else
  164.         qsort ((char *) lines, cur, sizeof (char *), compare);
  165. #endif
  166.  
  167.         if (! (fp = fopen (*argv, "w"))) {
  168.             perror (*argv);
  169.             continue;
  170.         }
  171.         for (max = cur, cur = 0;cur < max;cur++) {
  172.             fputs (lines[cur], fp);
  173.             putc ('\n', fp);
  174.         }
  175.  
  176.         fflush (fp);
  177.         fclose (fp);
  178.         free (lines);
  179.         free (buf);
  180.     }
  181.     exit (0);
  182. }
  183.